/*-------------------------------------------------------------------------
 *
 * spgvacuum.c
 *	  vacuum for SP-GiST
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/spgist/spgvacuum.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/genam.h"
#include "access/spgist_private.h"
#include "access/spgxlog.h"
#include "access/transam.h"
#include "access/xloginsert.h"
#include "catalog/storage_xlog.h"
#include "commands/vacuum.h"
#include "miscadmin.h"
#include "storage/bufmgr.h"
#include "storage/indexfsm.h"
#include "storage/lmgr.h"
#include "utils/snapmgr.h"

#ifdef FDD
#ifdef NOT_USED 
//解决打开NOT_USED编译宏后，RelationTruncate函数没有声明的问题
#include "catalog/storage.h"
#endif
#endif

/* 需要重新访问的TID的待处理列表中的条目 */
typedef struct spgVacPendingItem
{
	ItemPointerData tid;		/* 访问的重定向目标 */
	bool		done;			/* 我们处理过这个吗？ */
	struct spgVacPendingItem *next; /* 列表链接 */
} spgVacPendingItem;

/* 垃圾回收操作的本地状态 */
typedef struct spgBulkDeleteState
{
	/* 传递给spgvacuumscan的参数 */
	IndexVacuumInfo *info;
	IndexBulkDeleteResult *stats;
	IndexBulkDeleteCallback callback;
	void	   *callback_state;

	/* 额外的工作状态 */
	SpGistState spgstate;		/* 需要一个的SPGiST操作 */
	spgVacPendingItem *pendingList; /* 我们需要（重新）访问的TID */
	TransactionId myXmin;		/* 用于检测新添加的重定向 */
	BlockNumber lastFilledBlock;	/* 最后一个不可删除的块 */
} spgBulkDeleteState;


/*
 * 如果TID不在待处理列表中，则将其添加到待处理列表。
 *
 * 请注意，新项目始终附加到列表的末尾；这
 * 确保列表的扫描不会遗漏在扫描过程中添加的项目。
 */
static void fc_spgAddPendingTID(spgBulkDeleteState *fc_bds, ItemPointer fc_tid)
{
	spgVacPendingItem *fc_pitem;
	spgVacPendingItem **fc_listLink;

	/* 在列表中搜索现有条目 */
	fc_listLink = &fc_bds->pendingList;
	while (*fc_listLink != NULL)
	{
		fc_pitem = *fc_listLink;
		if (ItemPointerEquals(fc_tid, &fc_pitem->tid))
			return;				/* 已经在列表中，不做任何操作 */
		fc_listLink = &fc_pitem->next;
	}
	/* 不在那儿，所以附加新条目 */
	fc_pitem = (spgVacPendingItem *) palloc(sizeof(spgVacPendingItem));
	fc_pitem->tid = *fc_tid;
	fc_pitem->done = false;
	fc_pitem->next = NULL;
	*fc_listLink = fc_pitem;
}

/*
 * 清除待处理列表
 */
static void fc_spgClearPendingList(spgBulkDeleteState *fc_bds)
{
	spgVacPendingItem *fc_pitem;
	spgVacPendingItem *fc_nitem;

	for (fc_pitem = fc_bds->pendingList; fc_pitem != NULL; fc_pitem = fc_nitem)
	{
		fc_nitem = fc_pitem->next;
		/* 列表中的所有项目应该都已处理 */
		Assert(fc_pitem->done);
		pfree(fc_pitem);
	}
	fc_bds->pendingList = NULL;
}

/*
 * 垃圾回收常规（非根）叶子页面
 *
 * 我们必须删除被VACUUM目标删除的元组，
 * 但不移动任何被外部链接引用的元组；我们假设
 * 那些是链的头部。
 *
 * 如果我们发现一个由并发运行的事务创建的重定向，
 * 我们必须将其目标TID添加到待处理列表中。 （我们并不试图立即访问
 * 目标，首先是因为我们不希望VACUUM同时锁定多个缓冲区，其次是因为
 * spgAddPendingTID中的重复过滤逻辑对于确保在连续的
 * 并发插入中不会陷入无限循环是有用的。）
 *
 * 如果forPending为真，我们正在检查该页面，因为
 * 追踪重定向链接，而不是作为正常顺序扫描的一部分。
 * 我们仍然正常进行页面的垃圾回收，但我们不会增加
 * 有效元组的统计数据；否则我们会重复计算那些元组，因为该页面
 * 已经在顺序扫描中被访问过或将被访问。
 */
static void fc_vacuumLeafPage(spgBulkDeleteState *fc_bds, Relation fc_index, Buffer fc_buffer,
			   bool fc_forPending)
{
	Page		fc_page = BufferGetPage(fc_buffer);
	spgxlogVacuumLeaf fc_xlrec;
	OffsetNumber fc_toDead[MaxIndexTuplesPerPage];
	OffsetNumber fc_toPlaceholder[MaxIndexTuplesPerPage];
	OffsetNumber fc_moveSrc[MaxIndexTuplesPerPage];
	OffsetNumber fc_moveDest[MaxIndexTuplesPerPage];
	OffsetNumber fc_chainSrc[MaxIndexTuplesPerPage];
	OffsetNumber fc_chainDest[MaxIndexTuplesPerPage];
	OffsetNumber fc_predecessor[MaxIndexTuplesPerPage + 1];
	bool		fc_deletable[MaxIndexTuplesPerPage + 1];
	int			fc_nDeletable;
	OffsetNumber fc_i,
				fc_max = PageGetMaxOffsetNumber(fc_page);

	memset(fc_predecessor, 0, sizeof(fc_predecessor));
	memset(fc_deletable, 0, sizeof(fc_deletable));
	fc_nDeletable = 0;

	/* 扫描页面，识别需要删除的元组，累积统计数据 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_max; fc_i++)
	{
		SpGistLeafTuple fc_lt;

		fc_lt = (SpGistLeafTuple) PageGetItem(fc_page,
										   PageGetItemId(fc_page, fc_i));
		if (fc_lt->tupstate == SPGIST_LIVE)
		{
			Assert(ItemPointerIsValid(&fc_lt->heapPtr));

			if (fc_bds->callback(&fc_lt->heapPtr, fc_bds->callback_state))
			{
				fc_bds->stats->tuples_removed += 1;
				fc_deletable[fc_i] = true;
				fc_nDeletable++;
			}
			else
			{
				if (!fc_forPending)
					fc_bds->stats->num_index_tuples += 1;
			}

			/* 形成前驱映射 */
			if (SGLT_GET_NEXTOFFSET(fc_lt) != InvalidOffsetNumber)
			{
				/* 对受损链链接的偏执 */
				if (SGLT_GET_NEXTOFFSET(fc_lt) < FirstOffsetNumber ||
					SGLT_GET_NEXTOFFSET(fc_lt) > fc_max ||
					fc_predecessor[SGLT_GET_NEXTOFFSET(fc_lt)] != InvalidOffsetNumber)
					elog(ERROR, "inconsistent tuple chain links in page %u of index \"%s\"",
						 BufferGetBlockNumber(fc_buffer),
						 RelationGetRelationName(fc_index));
				fc_predecessor[SGLT_GET_NEXTOFFSET(fc_lt)] = fc_i;
			}
		}
		else if (fc_lt->tupstate == SPGIST_REDIRECT)
		{
			SpGistDeadTuple fc_dt = (SpGistDeadTuple) fc_lt;

			Assert(SGLT_GET_NEXTOFFSET(fc_dt) == InvalidOffsetNumber);
			Assert(ItemPointerIsValid(&fc_dt->pointer));

			/*
			 * 如果重定向自VACUUM开始以来可能发生，则将目标TID添加到待处理列表。
			 * （如果xid无效，则假设它
			 * 必须在VACUUM开始之前发生，因为REINDEX
			 * 同时锁定VACUUM。）
			 *
			 * 注意：我们可以通过查看xid是否
			 * 根据活动快照为“正在运行”来进行更严格的测试；但snapmgr.c
			 * 目前没有导出合适的API，并且不完全
			 * 清楚更严格的测试是否值得消耗周期。
			 */
			if (TransactionIdFollowsOrEquals(fc_dt->xid, fc_bds->myXmin))
				fc_spgAddPendingTID(fc_bds, &fc_dt->pointer);
		}
		else
		{
			Assert(SGLT_GET_NEXTOFFSET(fc_lt) == InvalidOffsetNumber);
		}
	}

	if (fc_nDeletable == 0)
		return;					/* 没有更多的工作要做 */

	/*----------
	 * 确定我们需要做的事情。我们与实际修改页面分开执行这一步，主要是为了获得可以写入WAL的表示，然后重放代码可以执行完全相同的操作。此步骤的输出包含六个数组，描述四种操作，按以下顺序执行：
	 *
	 * toDead[]: 要被替换为DEAD元组的元组编号
	 * toPlaceholder[]: 要被替换为PLACEHOLDER元组的元组编号
	 * moveSrc[]: 需要被重新定位到另一个偏移的新元组编号（替换那里的元组），然后被替换为PLACEHOLDER元组
	 * moveDest[]: moveSrc元组的新位置
	 * chainSrc[]: 其链链接（nextOffset）需要更新的元组编号
	 * chainDest[]: chainSrc成员的nextOffset新值
	 *
	 * 通过处理元组链来确定我们需要做的事情是最简单的，因此我们遍历所有元组（不仅仅是可删除的元组！）以识别链头，然后追踪每个链并为链内的可删除元组创建工作项条目。
	 *----------
	 */
	fc_xlrec.nDead = fc_xlrec.nPlaceholder = fc_xlrec.nMove = fc_xlrec.nChain = 0;

	for (fc_i = FirstOffsetNumber; fc_i <= fc_max; fc_i++)
	{
		SpGistLeafTuple fc_head;
		bool		fc_interveningDeletable;
		OffsetNumber fc_prevLive;
		OffsetNumber fc_j;

		fc_head = (SpGistLeafTuple) PageGetItem(fc_page,
											 PageGetItemId(fc_page, fc_i));
		if (fc_head->tupstate != SPGIST_LIVE)
			continue;			/* 不能是链成员 */
		if (fc_predecessor[fc_i] != 0)
			continue;			/* 不是链头 */

		/* 初始化... */
		fc_interveningDeletable = false;
		fc_prevLive = fc_deletable[fc_i] ? InvalidOffsetNumber : fc_i;

		/* 扫描链... */
		fc_j = SGLT_GET_NEXTOFFSET(fc_head);
		while (fc_j != InvalidOffsetNumber)
		{
			SpGistLeafTuple fc_lt;

			fc_lt = (SpGistLeafTuple) PageGetItem(fc_page,
											   PageGetItemId(fc_page, fc_j));
			if (fc_lt->tupstate != SPGIST_LIVE)
			{
				/* 链中的所有元组应该是活动的 */
				elog(ERROR, "unexpected SPGiST tuple state: %d",
					 fc_lt->tupstate);
			}

			if (fc_deletable[fc_j])
			{
				/* 此元组应被替换为占位符 */
				fc_toPlaceholder[fc_xlrec.nPlaceholder] = fc_j;
				fc_xlrec.nPlaceholder++;
				/* 前一个活动元组的链链接需要更新 */
				fc_interveningDeletable = true;
			}
			else if (fc_prevLive == InvalidOffsetNumber)
			{
				/*
				 * 这是链中的第一个活动元组。它必须移动到
				 * 头部位置。
				 */
				fc_moveSrc[fc_xlrec.nMove] = fc_j;
				fc_moveDest[fc_xlrec.nMove] = fc_i;
				fc_xlrec.nMove++;
				/* 链更新将在移动后应用 */
				fc_prevLive = fc_i;
				fc_interveningDeletable = false;
			}
			else
			{
				/*
				 * 第二个或更晚的活动元组。如果有间隙，则安排将其重新链入
				 * 前一个活动元组。
				 */
				if (fc_interveningDeletable)
				{
					fc_chainSrc[fc_xlrec.nChain] = fc_prevLive;
					fc_chainDest[fc_xlrec.nChain] = fc_j;
					fc_xlrec.nChain++;
				}
				fc_prevLive = fc_j;
				fc_interveningDeletable = false;
			}

			fc_j = SGLT_GET_NEXTOFFSET(fc_lt);
		}

		if (fc_prevLive == InvalidOffsetNumber)
		{
			/* 链完全可移除，因此我们需要一个DEAD元组 */
			fc_toDead[fc_xlrec.nDead] = fc_i;
			fc_xlrec.nDead++;
		}
		else if (fc_interveningDeletable)
		{
			/* 链末尾有一个或多个删除，因此关闭它 */
			fc_chainSrc[fc_xlrec.nChain] = fc_prevLive;
			fc_chainDest[fc_xlrec.nChain] = InvalidOffsetNumber;
			fc_xlrec.nChain++;
		}
	}

	/* 安全检查... */
	if (fc_nDeletable != fc_xlrec.nDead + fc_xlrec.nPlaceholder + fc_xlrec.nMove)
		elog(ERROR, "inconsistent counts of deletable tuples");

	/* 执行更新 */
	START_CRIT_SECTION();

	spgPageIndexMultiDelete(&fc_bds->spgstate, fc_page,
							fc_toDead, fc_xlrec.nDead,
							SPGIST_DEAD, SPGIST_DEAD,
							InvalidBlockNumber, InvalidOffsetNumber);

	spgPageIndexMultiDelete(&fc_bds->spgstate, fc_page,
							fc_toPlaceholder, fc_xlrec.nPlaceholder,
							SPGIST_PLACEHOLDER, SPGIST_PLACEHOLDER,
							InvalidBlockNumber, InvalidOffsetNumber);

	/*
	 * 我们通过交换源元组和目标元组的行指针来实现移动步骤，然后用
	 * 占位符替换新源元组。这可能与页面数据表示过于友好，但速度快，并且在需要重新定位的元组较大时不会导致页面溢出。
	 */
	for (fc_i = 0; fc_i < fc_xlrec.nMove; fc_i++)
	{
		ItemId		fc_idSrc = PageGetItemId(fc_page, fc_moveSrc[fc_i]);
		ItemId		fc_idDest = PageGetItemId(fc_page, fc_moveDest[fc_i]);
		ItemIdData	fc_tmp;

		fc_tmp = *fc_idSrc;
		*fc_idSrc = *fc_idDest;
		*fc_idDest = fc_tmp;
	}

	spgPageIndexMultiDelete(&fc_bds->spgstate, fc_page,
							fc_moveSrc, fc_xlrec.nMove,
							SPGIST_PLACEHOLDER, SPGIST_PLACEHOLDER,
							InvalidBlockNumber, InvalidOffsetNumber);

	for (fc_i = 0; fc_i < fc_xlrec.nChain; fc_i++)
	{
		SpGistLeafTuple fc_lt;

		fc_lt = (SpGistLeafTuple) PageGetItem(fc_page,
										   PageGetItemId(fc_page, fc_chainSrc[fc_i]));
		Assert(fc_lt->tupstate == SPGIST_LIVE);
		SGLT_SET_NEXTOFFSET(fc_lt, fc_chainDest[fc_i]);
	}

	MarkBufferDirty(fc_buffer);

	if (RelationNeedsWAL(fc_index))
	{
		XLogRecPtr	fc_recptr;

		XLogBeginInsert();

		STORE_STATE(&fc_bds->spgstate, fc_xlrec.stateSrc);

		XLogRegisterData((char *) &fc_xlrec, SizeOfSpgxlogVacuumLeaf);
		/* sizeof(xlrec) 应该是 sizeof(OffsetNumber) 的整数倍 */
		XLogRegisterData((char *) fc_toDead, sizeof(OffsetNumber) * fc_xlrec.nDead);
		XLogRegisterData((char *) fc_toPlaceholder, sizeof(OffsetNumber) * fc_xlrec.nPlaceholder);
		XLogRegisterData((char *) fc_moveSrc, sizeof(OffsetNumber) * fc_xlrec.nMove);
		XLogRegisterData((char *) fc_moveDest, sizeof(OffsetNumber) * fc_xlrec.nMove);
		XLogRegisterData((char *) fc_chainSrc, sizeof(OffsetNumber) * fc_xlrec.nChain);
		XLogRegisterData((char *) fc_chainDest, sizeof(OffsetNumber) * fc_xlrec.nChain);

		XLogRegisterBuffer(0, fc_buffer, REGBUF_STANDARD);

		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_VACUUM_LEAF);

		PageSetLSN(fc_page, fc_recptr);
	}

	END_CRIT_SECTION();
}

/*
 * 当根页面也是叶子时进行清理
 *
 * 在根页面上，我们仅删除任何死的叶子元组；没有复杂的操作
 */
static void fc_vacuumLeafRoot(spgBulkDeleteState *fc_bds, Relation fc_index, Buffer fc_buffer)
{
	Page		fc_page = BufferGetPage(fc_buffer);
	spgxlogVacuumRoot fc_xlrec;
	OffsetNumber fc_toDelete[MaxIndexTuplesPerPage];
	OffsetNumber fc_i,
				fc_max = PageGetMaxOffsetNumber(fc_page);

	fc_xlrec.nDelete = 0;

	/* 扫描页面，识别需要删除的元组，累积统计数据 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_max; fc_i++)
	{
		SpGistLeafTuple fc_lt;

		fc_lt = (SpGistLeafTuple) PageGetItem(fc_page,
										   PageGetItemId(fc_page, fc_i));
		if (fc_lt->tupstate == SPGIST_LIVE)
		{
			Assert(ItemPointerIsValid(&fc_lt->heapPtr));

			if (fc_bds->callback(&fc_lt->heapPtr, fc_bds->callback_state))
			{
				fc_bds->stats->tuples_removed += 1;
				fc_toDelete[fc_xlrec.nDelete] = fc_i;
				fc_xlrec.nDelete++;
			}
			else
			{
				fc_bds->stats->num_index_tuples += 1;
			}
		}
		else
		{
			/* 根上的所有元组应该是活动的 */
			elog(ERROR, "unexpected SPGiST tuple state: %d",
				 fc_lt->tupstate);
		}
	}

	if (fc_xlrec.nDelete == 0)
		return;					/* 没有更多的工作要做 */

	/* 执行更新 */
	START_CRIT_SECTION();

	/* 元组编号是有序的，所以我们可以使用 PageIndexMultiDelete */
	PageIndexMultiDelete(fc_page, fc_toDelete, fc_xlrec.nDelete);

	MarkBufferDirty(fc_buffer);

	if (RelationNeedsWAL(fc_index))
	{
		XLogRecPtr	fc_recptr;

		XLogBeginInsert();

		/* 准备 WAL 记录 */
		STORE_STATE(&fc_bds->spgstate, fc_xlrec.stateSrc);

		XLogRegisterData((char *) &fc_xlrec, SizeOfSpgxlogVacuumRoot);
		/* sizeof(xlrec) 应该是 sizeof(OffsetNumber) 的整数倍 */
		XLogRegisterData((char *) fc_toDelete,
						 sizeof(OffsetNumber) * fc_xlrec.nDelete);

		XLogRegisterBuffer(0, fc_buffer, REGBUF_STANDARD);

		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_VACUUM_ROOT);

		PageSetLSN(fc_page, fc_recptr);
	}

	END_CRIT_SECTION();
}

/*
 * 清理给定页面上的重定向和占位符元组
 *
 * 重定向元组在足够老时可以标记为占位符。
 * 如果删除不影响非占位符元组的偏移，则可以移除占位符元组。
 *
 * 与上面的例程不同，这个功能可以在叶子页和内部页面上工作。
 */
static void fc_vacuumRedirectAndPlaceholder(Relation fc_index, Buffer fc_buffer)
{
	Page		fc_page = BufferGetPage(fc_buffer);
	SpGistPageOpaque fc_opaque = SpGistPageGetOpaque(fc_page);
	OffsetNumber fc_i,
				fc_max = PageGetMaxOffsetNumber(fc_page),
				fc_firstPlaceholder = InvalidOffsetNumber;
	bool		fc_hasNonPlaceholder = false;
	bool		fc_hasUpdate = false;
	OffsetNumber fc_itemToPlaceholder[MaxIndexTuplesPerPage];
	OffsetNumber fc_itemnos[MaxIndexTuplesPerPage];
	spgxlogVacuumRedirect fc_xlrec;
	GlobalVisState *fc_vistest;

	fc_xlrec.nToPlaceholder = 0;
	fc_xlrec.newestRedirectXid = InvalidTransactionId;

	/* XXX: 提供堆关系将允许更多的修剪 */
	fc_vistest = GlobalVisTestFor(NULL);

	START_CRIT_SECTION();

	/*
	 * 向后扫描以将旧重定向元组转换为占位符元组，
	 * 同时识别最后一个非占位符元组的位置。
	 */
	for (fc_i = fc_max;
		 fc_i >= FirstOffsetNumber &&
		 (fc_opaque->nRedirection > 0 || !fc_hasNonPlaceholder);
		 fc_i--)
	{
		SpGistDeadTuple fc_dt;

		fc_dt = (SpGistDeadTuple) PageGetItem(fc_page, PageGetItemId(fc_page, fc_i));

		/*
		 * 如果没有任何正在进行的索引扫描指向它，我们可以将
		 * 重定向转换为占位符。这样的索引扫描必须在
		 * 其快照视图中看到重定向的XID仍在运行的事务中，因此
		 * 将XID与全局xmin进行比较是一个保守安全的测试。
		 * 如果XID无效，它必须是由REINDEX CONCURRENTLY插入的，
		 * 所以我们可以立即删除它。
		 */
		if (fc_dt->tupstate == SPGIST_REDIRECT &&
			(!TransactionIdIsValid(fc_dt->xid) ||
			 GlobalVisTestIsRemovableXid(fc_vistest, fc_dt->xid)))
		{
			fc_dt->tupstate = SPGIST_PLACEHOLDER;
			Assert(fc_opaque->nRedirection > 0);
			fc_opaque->nRedirection--;
			fc_opaque->nPlaceholder++;

			/* 记住被移除的重定向中最新的XID */
			if (!TransactionIdIsValid(fc_xlrec.newestRedirectXid) ||
				TransactionIdPrecedes(fc_xlrec.newestRedirectXid, fc_dt->xid))
				fc_xlrec.newestRedirectXid = fc_dt->xid;

			ItemPointerSetInvalid(&fc_dt->pointer);

			fc_itemToPlaceholder[fc_xlrec.nToPlaceholder] = fc_i;
			fc_xlrec.nToPlaceholder++;

			fc_hasUpdate = true;
		}

		if (fc_dt->tupstate == SPGIST_PLACEHOLDER)
		{
			if (!fc_hasNonPlaceholder)
				fc_firstPlaceholder = fc_i;
		}
		else
		{
			fc_hasNonPlaceholder = true;
		}
	}

	/*
	 * 页末的任何占位符元组都可以安全地移除。
	 * 然而，我们不能在最后一个非占位符之前移除，因为我们
	 * 不能更改非占位符元组的偏移量编号。
	 */
	if (fc_firstPlaceholder != InvalidOffsetNumber)
	{
		/*
		 * 我们不将这个数组存储到rdata中，因为很容易重新创建。
		 */
		for (fc_i = fc_firstPlaceholder; fc_i <= fc_max; fc_i++)
			fc_itemnos[fc_i - fc_firstPlaceholder] = fc_i;

		fc_i = fc_max - fc_firstPlaceholder + 1;
		Assert(fc_opaque->nPlaceholder >= fc_i);
		fc_opaque->nPlaceholder -= fc_i;

		/* 该数组肯定是已排序的，因此可以使用PageIndexMultiDelete */
		PageIndexMultiDelete(fc_page, fc_itemnos, fc_i);

		fc_hasUpdate = true;
	}

	fc_xlrec.firstPlaceholder = fc_firstPlaceholder;

	if (fc_hasUpdate)
		MarkBufferDirty(fc_buffer);

	if (fc_hasUpdate && RelationNeedsWAL(fc_index))
	{
		XLogRecPtr	fc_recptr;

		XLogBeginInsert();

		XLogRegisterData((char *) &fc_xlrec, SizeOfSpgxlogVacuumRedirect);
		XLogRegisterData((char *) fc_itemToPlaceholder,
						 sizeof(OffsetNumber) * fc_xlrec.nToPlaceholder);

		XLogRegisterBuffer(0, fc_buffer, REGBUF_STANDARD);

		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_VACUUM_REDIRECT);

		PageSetLSN(fc_page, fc_recptr);
	}

	END_CRIT_SECTION();
}

/*
 * 在批量删除扫描期间处理一个页面
 */
static void fc_spgvacuumpage(spgBulkDeleteState *fc_bds, BlockNumber fc_blkno)
{
	Relation	fc_index = fc_bds->info->index;
	Buffer		fc_buffer;
	Page		fc_page;

	/* 在不持有任何缓冲区锁的情况下调用vacuum_delay_point */
	vacuum_delay_point();

	fc_buffer = ReadBufferExtended(fc_index, MAIN_FORKNUM, fc_blkno,
								RBM_NORMAL, fc_bds->info->strategy);
	LockBuffer(fc_buffer, BUFFER_LOCK_EXCLUSIVE);
	fc_page = (Page) BufferGetPage(fc_buffer);

	if (PageIsNew(fc_page))
	{
		/*
		 * 我们发现了一个全零页，这可能发生在数据库
		 * 在扩展文件后崩溃时。回收它。
		 */
	}
	else if (PageIsEmpty(fc_page))
	{
		/* 无需操作 */
	}
	else if (SpGistPageIsLeaf(fc_page))
	{
		if (SpGistBlockIsRoot(fc_blkno))
		{
			fc_vacuumLeafRoot(fc_bds, fc_index, fc_buffer);
			/* 不需要vacuumRedirectAndPlaceholder */
		}
		else
		{
			fc_vacuumLeafPage(fc_bds, fc_index, fc_buffer, false);
			fc_vacuumRedirectAndPlaceholder(fc_index, fc_buffer);
		}
	}
	else
	{
		/* 内部页面 */
		fc_vacuumRedirectAndPlaceholder(fc_index, fc_buffer);
	}

	/*
	 * 根页面绝不能被删除，也不能在FSM中标记为可用，
	 * 因为我们不希望它们在搜索放置新元组的地方时被返回。
	 * 否则，检查空页面，确保FSM对此有所了解。
	 */
	if (!SpGistBlockIsRoot(fc_blkno))
	{
		if (PageIsNew(fc_page) || PageIsEmpty(fc_page))
		{
			RecordFreeIndexPage(fc_index, fc_blkno);
			fc_bds->stats->pages_deleted++;
		}
		else
		{
			SpGistSetLastUsedPage(fc_index, fc_buffer);
			fc_bds->lastFilledBlock = fc_blkno;
		}
	}

	UnlockReleaseBuffer(fc_buffer);
}

/*
 * 处理主扫描之间的待处理-TID列表
 */
static void fc_spgprocesspending(spgBulkDeleteState *fc_bds)
{
	Relation	fc_index = fc_bds->info->index;
	spgVacPendingItem *fc_pitem;
	spgVacPendingItem *fc_nitem;
	BlockNumber fc_blkno;
	Buffer		fc_buffer;
	Page		fc_page;

	for (fc_pitem = fc_bds->pendingList; fc_pitem != NULL; fc_pitem = fc_pitem->next)
	{
		if (fc_pitem->done)
			continue;			/* 忽略已经完成的条目 */

		/* 在不持有任何缓冲区锁的情况下调用vacuum_delay_point */
		vacuum_delay_point();

		/* 检查引用页面 */
		fc_blkno = ItemPointerGetBlockNumber(&fc_pitem->tid);
		fc_buffer = ReadBufferExtended(fc_index, MAIN_FORKNUM, fc_blkno,
									RBM_NORMAL, fc_bds->info->strategy);
		LockBuffer(fc_buffer, BUFFER_LOCK_EXCLUSIVE);
		fc_page = (Page) BufferGetPage(fc_buffer);

		if (PageIsNew(fc_page) || SpGistPageIsDeleted(fc_page))
		{
			/* 这可能不应该发生，但忽略它 */
		}
		else if (SpGistPageIsLeaf(fc_page))
		{
			if (SpGistBlockIsRoot(fc_blkno))
			{
				/* 这绝对不应该发生 */
				elog(ERROR, "redirection leads to root page of index \"%s\"",
					 RelationGetRelationName(fc_index));
			}

			/* 处理任何可删除的元组 */
			fc_vacuumLeafPage(fc_bds, fc_index, fc_buffer, true);
			/* 在我们这里的时候也可以做这个 */
			fc_vacuumRedirectAndPlaceholder(fc_index, fc_buffer);

			SpGistSetLastUsedPage(fc_index, fc_buffer);

			/*
			 * 我们不仅可以将此项标记为完成，还可以将指向
			 * 同一页面的任何后续项标记为完成，因为我们已经清理了整页。
			 */
			fc_pitem->done = true;
			for (fc_nitem = fc_pitem->next; fc_nitem != NULL; fc_nitem = fc_nitem->next)
			{
				if (ItemPointerGetBlockNumber(&fc_nitem->tid) == fc_blkno)
					fc_nitem->done = true;
			}
		}
		else
		{
			/*
			 * 在内部页面上，访问引用的内部元组，并将其所有
			 * 下行链接添加到待处理列表。我们可能在同一页面上
			 * 对多个内部元组有待处理项（实际上，考虑到
			 * 空间分配的工作方式，这相当可能），所以在我们这里
			 * 一并处理。
			 */
			for (fc_nitem = fc_pitem; fc_nitem != NULL; fc_nitem = fc_nitem->next)
			{
				if (fc_nitem->done)
					continue;
				if (ItemPointerGetBlockNumber(&fc_nitem->tid) == fc_blkno)
				{
					OffsetNumber fc_offset;
					SpGistInnerTuple fc_innerTuple;

					fc_offset = ItemPointerGetOffsetNumber(&fc_nitem->tid);
					fc_innerTuple = (SpGistInnerTuple) PageGetItem(fc_page,
																PageGetItemId(fc_page, fc_offset));
					if (fc_innerTuple->tupstate == SPGIST_LIVE)
					{
						SpGistNodeTuple fc_node;
						int			fc_i;

						SGITITERATE(fc_innerTuple, fc_i, fc_node)
						{
							if (ItemPointerIsValid(&fc_node->t_tid))
								fc_spgAddPendingTID(fc_bds, &fc_node->t_tid);
						}
					}
					else if (fc_innerTuple->tupstate == SPGIST_REDIRECT)
					{
						/* 将注意力转移到重定向点 */
						fc_spgAddPendingTID(fc_bds,
										 &((SpGistDeadTuple) fc_innerTuple)->pointer);
					}
					else
						elog(ERROR, "unexpected SPGiST tuple state: %d",
							 fc_innerTuple->tupstate);

					fc_nitem->done = true;
				}
			}
		}

		UnlockReleaseBuffer(fc_buffer);
	}

	fc_spgClearPendingList(fc_bds);
}

/*
 * 执行批量删除扫描
 */
static void fc_spgvacuumscan(spgBulkDeleteState *fc_bds)
{
	Relation	fc_index = fc_bds->info->index;
	bool		fc_needLock;
	BlockNumber fc_num_pages,
				fc_blkno;

	/* 完成设置 spgBulkDeleteState */
	initSpGistState(&fc_bds->spgstate, fc_index);
	fc_bds->pendingList = NULL;
	fc_bds->myXmin = GetActiveSnapshot()->xmin;
	fc_bds->lastFilledBlock = SPGIST_LAST_FIXED_BLKNO;

	/*
	 * 重置在扫描过程中将递增的计数；在单个 VACUUM 命令期间
	 * 进行多次扫描时需要
	 */
	fc_bds->stats->estimated_count = false;
	fc_bds->stats->num_index_tuples = 0;
	fc_bds->stats->pages_deleted = 0;

	/* 对于新的或临时关系，我们可以跳过锁定 */
	fc_needLock = !RELATION_IS_LOCAL(fc_index);

	/*
	 * 外部循环遍历所有索引页面，除了元页面，按物理顺序
	 * （我们希望内核能够配合提供提前读取以提高速度）。访问所有叶子页面
	 * 是至关重要的，包括在我们开始扫描后添加的页面，否则我们可能无法
	 * 删除一些可删除的元组。有关此内容的更详细注释，请参见 btvacuumscan()。
	 */
	fc_blkno = SPGIST_METAPAGE_BLKNO + 1;
	for (;;)
	{
		/* 获取当前关系长度 */
		if (fc_needLock)
			LockRelationForExtension(fc_index, ExclusiveLock);
		fc_num_pages = RelationGetNumberOfBlocks(fc_index);
		if (fc_needLock)
			UnlockRelationForExtension(fc_index, ExclusiveLock);

		/* 如果我们扫描了整个关系，则退出 */
		if (fc_blkno >= fc_num_pages)
			break;
		/* 遍历页面，然后循环回去重新检查长度 */
		for (; fc_blkno < fc_num_pages; fc_blkno++)
		{
			fc_spgvacuumpage(fc_bds, fc_blkno);
			/* 在每个页面后清空待处理列表 */
			if (fc_bds->pendingList != NULL)
				fc_spgprocesspending(fc_bds);
		}
	}

	/* 将本地 lastUsedPages 缓存传播到元块 */
	SpGistUpdateMetaPage(fc_index);

	/*
	 * 如果我们发现任何空页面（并在 FSM 中记录了它们），那么
	 * 强制更新上层 FSM 页面，以确保搜索者能够
	 * 找到它们。页面也可能在之前的扫描中被发现，所以这可能是浪费时间，但
	 * 相对于扫描索引来说，这样做的成本足够低，不应太大影响，并且
	 * 尽早确保空闲页面可用似乎是值得的。
	 *
	 * 注意，如果没有空页面，我们根本不必打扫 FSM。
	 */
	if (fc_bds->stats->pages_deleted > 0)
		IndexFreeSpaceMapVacuum(fc_index);

	/*
	 * 如果可能，截断索引
	 *
	 * XXX 禁用，因为由于可能的并发插入而不安全。
	 * 我们必须重新扫描页面以确保它们仍然为空，但
	 * 似乎不值得。注意，btree 也不这样做。
	 *
	 * 不截断的另一个原因是这可能会使元页面和其他后端
	 * 关系缓存中的缓存页面与空闲空间指针失效，即使它们指向不存在的页面。
	 * 添加 RelationGetNumberOfBlocks 调用来保护使用
	 * 这些指针的位置将会非常昂贵。
	 */
#ifdef NOT_USED
	if (fc_num_pages > fc_bds->lastFilledBlock + 1)
	{
		BlockNumber fc_lastBlock = fc_num_pages - 1;

		fc_num_pages = fc_bds->lastFilledBlock + 1;
		RelationTruncate(index, fc_num_pages);
#ifndef FDD
		//当前代版本代码，IndexBulkDeleteResult结构无pages_removed字段，所以注释
		fc_bds->stats->pages_removed += lastBlock - fc_bds->lastFilledBlock;
#endif
		fc_bds->stats->pages_deleted -= fc_lastBlock - fc_bds->lastFilledBlock;
	}
#endif

	/* 报告最终统计信息 */
	fc_bds->stats->num_pages = fc_num_pages;
	fc_bds->stats->pages_newly_deleted = fc_bds->stats->pages_deleted;
	fc_bds->stats->pages_free = fc_bds->stats->pages_deleted;
}

/*
 * 批量删除所有指向一组堆元组的索引条目。
 * 目标元组集通过一个回调例程指定，该例程指示
 * 是否任何给定的堆元组（通过 ItemPointer 标识）正在被删除。
 *
 * 结果：一个 palloc 的结构，包含 VACUUM 显示的统计信息。
 */
IndexBulkDeleteResult * spgbulkdelete(IndexVacuumInfo *fc_info, IndexBulkDeleteResult *fc_stats,
			  IndexBulkDeleteCallback fc_callback, void *fc_callback_state)
{
	spgBulkDeleteState fc_bds;

	/* 如果第一次遍历则分配统计信息，否则重用现有结构 */
	if (fc_stats == NULL)
		fc_stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
	fc_bds.info = fc_info;
	fc_bds.stats = fc_stats;
	fc_bds.callback = fc_callback;
	fc_bds.callback_state = fc_callback_state;

	fc_spgvacuumscan(&fc_bds);

	return fc_stats;
}

/* 在 spgvacuumcleanup 期间不删除任何元组的虚回调 */
static bool fc_dummy_callback(ItemPointer fc_itemptr, void *fc_state)
{
	return false;
}

/*
 * 后VACUUM清理。
 *
 * 结果：一个palloc'd结构包含VACUUM显示的统计信息。
 */
IndexBulkDeleteResult * spgvacuumcleanup(IndexVacuumInfo *fc_info, IndexBulkDeleteResult *fc_stats)
{
	spgBulkDeleteState fc_bds;

	/* 在ANALYZE ONLY模式下无操作 */
	if (fc_info->analyze_only)
		return fc_stats;

	/*
	 * 如果之前有一个批量删除过程，我们就不需要扫描索引。
	 * 否则，进行一次不会删除任何活动元组的扫描，但
	 * 可能仍会通过重定向/占位符清理
	 * 和/或 FSM 管理完成有用的工作，并在任何情况下提供统计信息。
	 */
	if (fc_stats == NULL)
	{
		fc_stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
		fc_bds.info = fc_info;
		fc_bds.stats = fc_stats;
		fc_bds.callback = fc_dummy_callback;
		fc_bds.callback_state = NULL;

		fc_spgvacuumscan(&fc_bds);
	}

	/*
	 * 我们很可能会被并发的元组移动欺骗，从而导致某些索引元组的双重计数，因此不相信任何超过
	 * 基础堆计数的总数……如果我们能准确知道这一点。否则，这可能只会使情况变得更糟。
	 */
	if (!fc_info->estimated_count)
	{
		if (fc_stats->num_index_tuples > fc_info->num_heap_tuples)
			fc_stats->num_index_tuples = fc_info->num_heap_tuples;
	}

	return fc_stats;
}
